package LeetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author attcat
 * ---做一个有趣的程序员
 * @date 2022-09-30 21:33
 * @description
 * 假设你正在爬楼梯 需要N阶梯才能到达楼顶
 * 每次你可以爬1或者2个台阶，你有多少种不同的方法可以爬到顶楼
 *给定N是一个正整数
 *
 */
public class LeetCode_70 {
    /****
     * 递归解法
     */
    private Map<Integer,Integer> storeMap=new HashMap<>();

    public int recursive(int n){
        //第一层有一种解答
        if(n==1){
            return 1;
        }
        //2层有2种解答
        if(n==2){
            return 2;
        }
        return recursive(n-1)+recursive(n-2);
    }

    public int recursiveAddmap(int n){
        if(n==1) return 1;
        if(n==2) return 2;
        if(null!=storeMap.get(n)){
            return storeMap.get(n);
        }else {
          int result=  recursiveAddmap(n-1)+recursiveAddmap(n-2);
            storeMap.put(n,result);
            return result;
        }
    }

    public  int clibfor(int n){
        if(n==1) return 1;
        if(n==2) return 2;
        int result =0;
        int pre=2;
        int prePre=1;
        for(int i=3;i<=n;++i){
            result=pre+prePre;
            prePre=pre;
            pre=result;
        }
        return result;
    }




    public static void main(String[] args) {
        LeetCode_70 leetcode_70=new LeetCode_70();

        System.out.println(leetcode_70.recursiveAddmap(20));
        System.out.println(leetcode_70.clibfor(20));
    }
}
